//<p>给你一个只包含 <code>'('</code> 和 <code>')'</code> 的字符串，找出最长有效（格式正确且连续）括号子串的长度。</p>
//
//<p> </p>
//
//<div class="original__bRMd">
//<div>
//<p><strong>示例 1：</strong></p>
//
//<pre>
//<strong>输入：</strong>s = "(()"
//<strong>输出：</strong>2
//<strong>解释：</strong>最长有效括号子串是 "()"
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>s = ")()())"
//<strong>输出：</strong>4
//<strong>解释：</strong>最长有效括号子串是 "()()"
//</pre>
//
//<p><strong>示例 3：</strong></p>
//
//<pre>
//<strong>输入：</strong>s = ""
//<strong>输出：</strong>0
//</pre>
//
//<p> </p>
//
//<p><strong>提示：</strong></p>
//
//<ul>
//	<li><code>0 <= s.length <= 3 * 10<sup>4</sup></code></li>
//	<li><code>s[i]</code> 为 <code>'('</code> 或 <code>')'</code></li>
//</ul>
//</div>
//</div>
//<div><div>Related Topics</div><div><li>栈</li><li>字符串</li><li>动态规划</li></div></div><br><div><li>👍 1819</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

import cn.hutool.json.JSONUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
 * 最长有效括号
 * @author DY Rising
 * @date 2022-05-10 17:18:35
 */
public class P32_LongestValidParentheses{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P32_LongestValidParentheses().new Solution();
        //System.out.println(solution.longestValidParentheses("()(()"));
        //System.out.println(solution.longestValidParentheses("()(())"));
        System.out.println(solution.longestValidParentheses(")(())"));
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestValidParentheses(String s) {
        if (s.length() < 2) return 0;
        char[] chars = s.toCharArray();
        Stack<Integer> stack = new Stack<>();
        int max = 0;
        stack.push(-1);
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty())
                    stack.push(i);
                else {
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        return  max;
    }


}
//leetcode submit region end(Prohibit modification and deletion)

}
